#include "linklist.h"

LinkList::LinkList()
{

    m_head = new LinkNode(0, nullptr); // 创建虚拟头结点
    m_tail = m_head;                   // 初始化尾指针
    m_size = 0;                        // 初始化链表元素个数为0
}

LinkList::~LinkList()
{
    while (m_size != 0)
    {
        linkListHeadDelete(); // 逐个删除节点
    }
    delete m_head; // 释放虚拟头节点
}
int LinkList::linkListHeadInsert(ELEMENT_TYPE data) // 链表头插
{
    return linkListAppointPosInsert(0, data); // 头插相当于在位置 0 插入
}

int LinkList::linkListTailInsert(ELEMENT_TYPE data) // 链表尾插
{
    return linkListAppointPosInsert(m_size, data); // 尾插相当于在末尾插入
}

int LinkList::linkListAppointPosInsert(int pos, ELEMENT_TYPE data) // 链表任意位置插入
{
    if (pos < 0 || pos > m_size) // 判断插入位置是否合法
    {
        return -1;
    }

    LinkNode *travelNode = m_head;
    for (int i = 0; i < pos; i++)
    {
        travelNode = travelNode->m_next; // 找到目标位置的前一个节点
    }

    LinkNode *newNode = new LinkNode(data, travelNode->m_next); // 创建新节点
    travelNode->m_next = newNode;

    // 如果插入位置是尾部，需要更新尾指针
    if (travelNode == m_tail)
    {
        m_tail = newNode; // 更新尾指针
    }

    m_size++; // 链表元素个数++,更新链表大小
    return 0;
}

void LinkList::travelListElement() // 遍历链表元素
{
    LinkNode *travelNode = m_head->m_next;
    while (travelNode)
    {
        cout << travelNode->m_data << "\t"; // 输出每个节点的数据
        travelNode = travelNode->m_next;
    }
    cout << endl;
}

int LinkList::linkListHeadDelete() // 链表头删
{
    if (m_size == 0)
    {
        return -1; // 链表为空，无法删除
    }

    LinkNode *toDelete = m_head->m_next;
    m_head->m_next = toDelete->m_next;

    if (m_size == 1)
    {                    // 如果链表只有一个节点
        m_tail = m_head; // 更新尾指针
    }

    delete toDelete; // 释放内存
    m_size--;
    return 0;
}
int LinkList::linkListTailDelete() // 链表尾删
{
    if (m_size == 0) // 判断链表是否为空
    {
        return -1;
    }

    LinkNode *travelNode = m_head;
    while (travelNode->m_next != m_tail)
    {
        travelNode = travelNode->m_next; // 找到倒数第二个节点
    }

    delete m_tail; // 删除尾节点
    m_tail = travelNode;
    m_tail->m_next = nullptr;

    m_size--;
    return 0;
}

int LinkList::linkListAppointPosDelete(int pos) // 链表任意位置删
{
    if (pos < 0 || pos >= m_size)
    {
        return -1;
    }

    LinkNode *travelNode = m_head;
    for (int i = 0; i < pos; i++)
    {
        travelNode = travelNode->m_next; // 找到目标位置的前一个节点
    }

    LinkNode *toDelete = travelNode->m_next;
    travelNode->m_next = toDelete->m_next;

    if (toDelete == m_tail) // 如果删除的是尾节点，更新尾指针
    {
        m_tail = travelNode; // 更新尾指针
    }
    else
    {
        while (pos)
        {
            travelNode = travelNode->m_next;
            pos--;
        }
        /*循环退出之后，travelNode是要删除的前一个节点。*/
        LinkNode *delNode = travelNode->m_next;
        travelNode->m_next = delNode->m_next;
        delNode->m_next->m_prev = travelNode;
    }

    delete toDelete; // 释放内存
    m_size--;
    return 0;
}
